# Сортировка

Сортировка — обычная операция как в жизни, так и в информатике.
В нашей повседневной жизни мы сортируем элементы, чтобы поиск был быстрее, это верно и в области компьютерных наук.
В конце концов, компьютеры существуют, чтобы помогать нам в повседневных задачах.
Сортировка может присутствовать на разных уровнях в зависимости от требований. 
Например, иногда нам может понадобиться отсортировать символ за символом. 
В других случаях нам может понадобиться отсортировать более крупные структуры, например профили компаний. 
Какой бы ни была причина, основной принцип сортировки остается прежним. 

Кроме того, существует два порядка сортировки — по возрастанию и по убыванию. 
Предположим, что нужно отсортировать n элементов: \\(a\_{1}, a\_{2}, a\_{3}, ..., a\_{n}\\). 
Когда эти элементы отсортированы в порядке возрастания, 
их отношение можно формально сформулировать как \\(a\_{1} \leq a\_{2} \leq a\_{3} \leq ... \leq a\_{n}\\). 
Точно так же их сортировка по убыванию может быть формально сформулирована 
как \\(a\_{1} \geq a\_{2} \geq a\_{3} \geq ... \geq a\_{n}\\).

## Сортировка пузырьком (bubble sort)

**Алгоритм:**

Алгоритм [сортировки пузырьком](https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC) 
состоит из повторяющихся проходов по сортируемому массиву. 
За каждый проход элементы последовательно сравниваются попарно 
и, если порядок в паре неверный, выполняется перестановка элементов. 
Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, 
что обмены больше не нужны, что означает — массив отсортирован. 
При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится 
на своё место в конце массива рядом с предыдущим «наибольшим элементом», 
а наименьший элемент перемещается на одну позицию к началу массива 
(«всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

**Оценка:**

- **Время**:
    - Худшее - \\(O(n^{2})\\)
    - Лучшее - \\(O(n)\\)
    - Среднее - \\(O(n^{2})\\)
- **Память** - \\(O(1)\\)

**Код:**

Реализация сортировки пузырьком может выглядеть так:

- `as` - часть неотсортированного списка, по которой ещё осталось попарно сравнить элементы
- `zs` - часть неотсортированного списка, по которой элементы уже попарно сравнены
- `bs` - отсортированная часть списка
- если неотсортированная часть пустая, то возвращаем результат `bs` - отсортированная часть
- если `as` состоит из одного элемента, то он - максимальный среди неотсортированной части
    - добавляем максимальный в начало списка `bs` и продолжаем попарное сравнение среди `zs`
- если `as` состоит из нескольких элементов, то сравниваем первые два между собой
    - меняем их местами при необходимости

```dotty
def bubbleSort[A: Ordering](list: List[A]): List[A] =
  @tailrec
  def loop(as: List[A], zs: List[A], sorted: List[A]): List[A] =
    as match
      case Nil       => sorted
      case h1 :: Nil => loop(zs, Nil, h1 :: sorted)
      case h1 :: h2 :: t =>
        if h1 > h2 then loop(h1 :: t, h2 :: zs, sorted)
        else loop(h2 :: t, h1 :: zs, sorted)

  loop(list, Nil, Nil)
  
bubbleSort(List(3, 1, 4, 2)) 
// List(1, 2, 3, 4)
```

**Метрики:**

Сортировка по возрастанию списка с 10000 элементами, расположенными по убыванию,
занимает 1,5 секунды.

```dotty
private val unsortedList: List[Int]   = (10_000 to 1 by -1).toList

@main def bubbleSortBench(): Unit =
  bubbleSort(unsortedList)
      
// CPU Time: 1450 ms
// Allocation memory size: 3,61 GB      
```

## Сортировка выбором (selection sort)

**Алгоритм:**

Шаги [алгоритма сортировки выбором](https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC):

- находим номер минимального значения в текущем списке
- производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

**Оценка:**

- **Время**:
  - Худшее - \\(O(n^{2})\\)
  - Лучшее - \\(O(n^{2})\\)
  - Среднее - \\(O(n^{2})\\)
- **Память** - \\(O(1)\\)

**Код:**

Реализация сортировки выбором может выглядеть так:

- вспомогательный метод `select` принимает следующие аргументы: 
    - `max` - текущий максимальный элемент
    - `tail` - часть неотсортированного списка, где осталось сравнить элементы с максимальным
    - `zs` - часть неотсортированного списка, каждый элемент которого не более максимального
    - `sorted` - отсортированная часть списка
- если `tail` пустой, то `max` - максимальный элемент в неотсортированной части списка
    - если `zs` тоже пустой, то неотсортированной части не осталось, возвращаем `max :: sorted` 
      (в отсортированной части `sorted` все элементы не менее `max`, 
      поэтому `max :: sorted` остается отсортированным по возрастанию)
    - если `zs` не пустой, то добавляем `max` к отсортированной части 
      и продолжаем поиск следующего максимального элемента среди `zs`
- если `tail` не пустой, то берем его заглавный элемент - `h`:
    - если `max` больше `h`, то добавляем `h` в просмотренный список `zs`
    - если нет, то добавляем `max` в просмотренный список `zs`
    - продолжаем поиск с "новым" максимальным элементом по оставшейся части `tail`

```dotty
def selectionSort[A: Ordering](list: List[A]): List[A] =
  @tailrec
  def loop(max: A, tail: List[A], zs: List[A], sorted: List[A]): List[A] =
    (tail, zs) match
      case (Nil, Nil)             => max :: sorted
      case (Nil, h :: t)          => loop(h, t, Nil, max :: sorted)
      case (h :: t, _) if max > h => loop(max, t, h :: zs, sorted)
      case (h :: t, _)            => loop(h, t, max :: zs, sorted)

  list match
    case Nil          => Nil
    case head :: tail => loop(head, tail, Nil, Nil)
      
selectionSort(List(3, 1, 4, 2))
// List(1, 2, 3, 4)
```

**Метрики:**

Сортировка по возрастанию списка с 10000 элементами, расположенными по убыванию,
занимает 2 секунды.

```dotty
private val unsortedList: List[Int]   = (10_000 to 1 by -1).toList

@main def selectionSortBench(): Unit =
  selectionSort(unsortedList)
      
// CPU Time: 1733 ms
// Allocation memory size: 3,61 GB      
```

## Сортировка вставками (insertion sort)

**Алгоритм:**

В начальный момент отсортированная последовательность пуста. 
На каждом шаге [алгоритма сортировки вставками](https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8)
выбирается один из элементов входных данных и помещается на нужную позицию в уже отсортированной последовательности до тех пор, 
пока набор входных данных не будет исчерпан. 
В любой момент времени в отсортированной последовательности элементы удовлетворяют требованиям к выходным данным алгоритма.

**Оценка:**

- **Время**:
  - Худшее - \\(O(n^{2})\\)
  - Лучшее - \\(O(n)\\) 
  - Среднее - \\(O(n^{2})\\)
- **Память** - \\(O(n)\\)

**Код:**

```dotty
def insertionSort[A: Ordering](list: List[A]): List[A] =
  @tailrec
  def sort(as: List[A], bs: List[A]): List[A] = as match
    case Nil    => bs
    case h :: t => sort(t, insert(h, bs))

  def insert(a: A, as: List[A]): List[A] = as match
    case h :: t if a > h => h :: insert(a, t)
    case _               => a :: as

  sort(list, Nil)
  
insertionSort(List(3, 1, 4, 2))
// List(1, 2, 3, 4)  
```

**Метрики:**

Сортировка по возрастанию списка с 10000 элементами, расположенными по убыванию,
занимает меньше секунды.

```dotty
private val unsortedList: List[Int]   = (10_000 to 1 by -1).toList

@main def insertionSortBench(): Unit =
  insertionSort(unsortedList)
      
// CPU Time: 288 ms
// Allocation memory size: 12,17 MB      
```

## Сортировка слиянием (merge sort)

**Алгоритм:**

[Алгоритм сортировки слиянием](https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC) выглядят так:

- сортируемый массив разбивается на две части примерно одинакового размера
- каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом
- два упорядоченных массива половинного размера соединяются в один

**Оценка:**

- **Время**:
  - Худшее - \\(O(n log(n))\\)
  - Лучшее - \\(O(n log(n))\\)
  - Среднее - \\(O(n log(n))\\)
- **Память** - \\(O(1)\\) для списка, \\(O(n)\\) для массива

**Код:**

Отличие от императивной реализации по умолчанию — это способ разделения списка на две части. 
Обычно это решается использованием длины списка, стоимость которой составляет O(n), 
поскольку требуется пройти от начала до конца. 
[В этой реализации](https://github.com/vkostyukov/scalacaster/blob/master/src/sort/MergeSort.scala) 
список разбивается на две равные части с помощью функции `halve`. 
Эта функция выполняет простую вещь — она берет первые два элемента списка 
и добавляет их в два отдельных списка, которые накапливают результат. 
Другими словами, функция добавляет все четные узлы в первую часть, 
а нечетные — во вторую. Это можно сделать за O(n).

```dotty
def mergeSort[A: Ordering](list: List[A]): List[A] =
  def halveAndSort(as: List[A]) = sort(halve(as))

  def sort(p: (List[A], List[A])): List[A] = p match
    case (Nil, Nil)       => Nil
    case (ha :: Nil, Nil) => ha :: Nil
    case (Nil, hb :: Nil) => hb :: Nil
    case (as, bs)         => merge(halveAndSort(as), halveAndSort(bs))

  def halve(as: List[A]): (List[A], List[A]) =
    @tailrec
    def loop(bs: List[A], fs: List[A], ss: List[A]): (List[A], List[A]) =
      bs match
        case f :: s :: r => loop(r, f :: fs, s :: ss)
        case f :: Nil    => (f :: fs, ss)
        case Nil         => (fs, ss)

    loop(as, Nil, Nil)

  def merge(as: List[A], bs: List[A]): List[A] =
    @tailrec
    def loop(cs: List[A], ds: List[A], r: List[A]): List[A] = (cs, ds) match
      case (Nil, Nil)      => r
      case (ha :: ta, Nil) => loop(ta, Nil, ha :: r)
      case (Nil, hb :: tb) => loop(Nil, tb, hb :: r)
      case (ha :: ta, hb :: tb) =>
        if ha < hb then loop(ta, ds, ha :: r)
        else loop(cs, tb, hb :: r)

    loop(as, bs, Nil).reverse

  halveAndSort(list)
end mergeSort

mergeSort(List(3, 1, 4, 2))
// List(1, 2, 3, 4)
```

**Метрики:**

Сортировка по возрастанию списка с 10000 элементами, расположенными по убыванию,
занимает меньше секунды.

```dotty
@main def quickSortBench(): Unit =
  quickSort(unsortedList)
      
// CPU Time: 264 ms
// Allocation memory size: 17,3 MB      
```

## Быстрая сортировка (quicksort)

**Алгоритм:**

Общая идея [алгоритма быстрой сортировки](https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0) состоит в следующем:

- выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. 
  От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
- сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, 
  следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
- для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы

**Оценка:**

- **Время**:
  - Худшее - \\(O(n^{2})\\)
  - Лучшее - \\(O(n log(n))\\)
  - Среднее - \\(O(n log(n))\\)
- **Память** - \\(O(n)\\)

**Код:**

```dotty
def quickSort[A: Ordering](list: List[A]): List[A] =
  def partitionAndSort(as: List[A]): List[A] =
    as match
      case Nil      => as
      case h :: Nil => as
      case _ =>
        val (l, p, g) = partition(as)
        partitionAndSort(l) ::: (p :: partitionAndSort(g))

  def partition(as: List[A]): (List[A], A, List[A]) =
    @tailrec
    def loop(
        p: A,
        as: List[A],
        l: List[A],
        g: List[A]
    ): (List[A], A, List[A]) =
      as match
        case Nil             => (l, p, g)
        case h :: t if h < p => loop(p, t, h :: l, g)
        case h :: t          => loop(p, t, l, h :: g)

    loop(as.head, as.tail, Nil, Nil)

  partitionAndSort(list)
end quickSort
      
quickSort(List(3, 1, 4, 2))      
// List(1, 2, 3, 4)      
```

**Метрики:**

Сортировка по возрастанию списка с 2500 элементами, расположенными по убыванию,
занимает меньше секунды.


```dotty
@main def quickSortBench(): Unit =
  quickSort((2500 to 1 by -1).toList)
      
// CPU Time: 260 ms
// Allocation memory size: 192,58 MB      
```

На бОльших списках вылетает `StackOverflowError`. 

---

**Ссылки:**

- [Bhim P. Upadhyaya - Data Structures and Algorithms with Scala](https://link.springer.com/book/10.1007/978-3-030-12561-5)
- [Scalacaster](https://github.com/vkostyukov/scalacaster/tree/master)
- [Никлаус Вирт - Алгоритмы + Структуры данных = Программы](https://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs)
